struct TwoSat {
	const static int N = 100005;
	vi g[N<<1]; stack<int> S;
	int n, pre[N<<1], dfn[N<<1], dfs_clock, sccn, sccno[N<<1], mark[N<<1];

	void init(int tot) {
		n = tot * 2;
		for (int i = 0; i < n; i+= 2)
			g[i].clear(), g[i^1].clear();
	}
	void add_Edge(int u, int uval, int v, int vval) {
		u = u * 2 + uval; v = v * 2 + vval;
		g[u^1].push_back(v); g[v^1].push_back(u);
	}
	void dfs_scc(int u) {
        pre[u] = dfn[u] = ++dfs_clock; S.push(u);
        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (!pre[v]) {
                dfs_scc(v); dfn[u] = min(dfn[u], dfn[v]);
            } else if (!sccno[v]) dfn[u] = min(dfn[u], pre[v]);
        }
        if (pre[u] == dfn[u]) {
            sccn++;
            while (1) {
                int x = S.top(); S.pop();
                sccno[x] = sccn;
                if (x == u) break;
		}}
	}
	void find_scc() {
        dfs_clock = sccn = 0;
        memset(sccno, 0, sizeof(sccno));
        memset(pre, 0, sizeof(pre));
        for (int i = 0; i < n; i++)
            if (!pre[i]) dfs_scc(i);
	}
	bool solve() {
	    find_scc();
        for (int i = 0; i < n; i += 2) {
            if (sccno[i] == sccno[i + 1]) return false;
            mark[i / 2] = (sccno[i] > sccno[i + 1]);
        }
        return true;
	}
};
